import math
from typing import List


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        #
        cnt = 0
        i = 1
        # 防止数据重复
        seen = {}

        # 回文数验证
        def validPalindrome(s: str) -> bool:
            l = 0
            r = len(s) - 1
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        while i < 10 ** 5:
            power = math.floor(math.log10(i))
            x = i
            r = 0
            while x > 0:
                r = r * 10 + (x % 10)
                x = x // 10
                Q = (i * 10 ** power + r % 10 ** power) ** 2

                if Q > int(right):
                    return cnt
                if Q >= int(left) and validPalindrome(str(Q)):
                    if Q not in seen:
                        cnt += 1
                        seen[Q] = True
                Q = (i * 10 ** (power + 1) + r) ** 2
                if Q >= int(left) and Q <= int(right) and validPalindrome(str(Q)):
                    if Q not in seen:
                        cnt += 1
                        seen[Q] = True
                i += 1
        return cnt


if __name__ == '__main__':

    solution = Solution()
    print(solution.superpalindromesInRange(4,1000))

# 如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
#
# 现在，给定两个正整数
# L
# 和
# R （以字符串形式表示），返回包含在范围[L, R]
# 中的超级回文数的数目。
# 示例：
#
# 输入：L = "4", R = "1000"
# 输出：4
# 解释：
# 4，9，121，以及
# 484
# 是超级回文数。
# 注意
# 676
# 不是一个超级回文数： 26 * 26 = 676，但是
# 26
# 不是回文数。
#
#
# 提示：
#
# 1 <= len(L) <= 18
# 1 <= len(R) <= 18
# L
# 和
# R
# 是表示[1, 10 ^ 18) 范围的整数的字符串。
# int(L) <= int(R)
